package com.veal98.tree;

import com.veal98.bean.TreeNode;

public class LowestCommonAncestorOfABinarySearchTree_235 {

    public static void main(String[] args) {

    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        if (root == p || root == q) {
            return root;
        }

        // p q 位于 root 左子树
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }

        if (root.val < p.val && root.val < q.val) {
            // p q 都位于 root 的右子树上
            return lowestCommonAncestor(root.right, p, q);
        }

        // p q 分居 root 的两侧, 则他俩的最近公共祖先结点为 root
        return root;
    }

}
